package algorithm;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.atomic.AtomicInteger;


import Main.Attribute;
import Main.OutPutter;

public class ID3 {
    	private final ArrayList<Attribute> attributes;
	private final Attribute goal;
	private Attribute examples;

    public ID3(ArrayList<Attribute> attributes, Attribute goal, Attribute examples) { //assumption
	this.attributes = attributes; 
	this.goal = goal;
	this.examples = examples;
    }

    /**
     * Main algorithm
     * @param exampleindex 
     * @param attributeslist
     */
    @SuppressWarnings("rawtypes")
    private TreeNode<String> id3(ArrayList<Integer> attribuIndex, ArrayList<Integer> exampIndex){
	if(exampIndex.size() == 0)
	    return null; 						
	else if(checkExamplesInSameClassification(exampIndex)){
	    String classification = goal.getDataAt(exampIndex.get(0)).toString();	//get classification based on current example index
	    return new TreeNode<String>(classification);
	}
	else if(attribuIndex.size() == 0)
	    return pluralityValue(exampIndex); 
	else{
	    
	    AtomicInteger indexindex = new AtomicInteger(); 	//keeps the index of attrIndex from dummpyEntropy's result
	    indexindex.set(-1);
	    int bestIndex= 		//Index of best attributes
		    calcEntropy(attribuIndex, attributes, exampIndex, indexindex); 	
	    Attribute best = attributes.get(bestIndex);
	    
	    TreeNode<String> tree = new TreeNode<String>(best.getName());		//creating a new tree trunk
	    attribuIndex.remove(indexindex.get()); 					//equivalent of Attribute - A in example program
	    for(String s : (ArrayList<String>) best.getDataTypes()){ 			//iterate through 
		ArrayList<Integer> subExampIndex = searchExamples(s, best, exampIndex); //Search for e
		TreeNode subtree = id3(attribuIndex, subExampIndex);
			if(subtree == null)						//if there are no subExampIndex, use current exampIndex
			    subtree =  pluralityValue(exampIndex);

		tree.addNode(s, subtree);
	    }
	    return tree;
	}
    }
    
    
    /***
     * Histogram of goal values
     * @param exIndex
     * @return
     */
    private TreeNode<String> pluralityValue(ArrayList<Integer> exIndex) {
	Map<String, Integer> histogram = new HashMap<String, Integer>(); 
	
	//Creating a histogram
	for(int i : exIndex){
	    Integer get = histogram.get(goal.getDataAt(i)); 
	    if(get == null)
		histogram.put(goal.getDataAt(i), 1);
	    else
		histogram.put(goal.getDataAt(i), get+1);
	    get = histogram.get(goal.getDataAt(i)); 
	}
	
	//Iterate through to find a max value
	Map.Entry<String, Integer> max = null;
	for(Map.Entry<String, Integer> val : histogram.entrySet())
	{
	    if (max == null || val.getValue().compareTo(max.getValue()) > 0)
	    {
		max = val;
	    }
	}
	return new TreeNode<String>(max.getKey());
    }

    /**
     * This program checks if remaining examples are in the same classification 
     * @param attrIndex
     * @param exIndex
     * @return
     */
    private boolean checkExamplesInSameClassification(
	    ArrayList<Integer> exIndex) {
	//Attribute goal = attributes.get(attributes.size() - 1); //get the goal attributes
	int b = -1;
	for(int i : exIndex){
	    if(b < 0){ 	//skip first loop
		b = i;
		continue; 
	    }
	    if(!goal.getDataAt(b).equals(goal.getDataAt(i))) //compare with last result
		return false;
		b = i;
	}
	return true;
    }

    /**
     * This method searches remaining index 
     * @param dataType The type of data we are looking for
     * @param best
     * @param index index of remaining examples.
     * @return
     */
    private ArrayList<Integer> searchExamples(String dataType, Attribute best, ArrayList<Integer> index ){
	
	ArrayList<Integer> result = new ArrayList<Integer>();
	for(Integer c : index){
	    if(best.getData()	//get all examples in this attribute
		    .get(c) 	//get remaining index of examples
		    .toString() //attempt to convert to String
		    .equals(dataType))
		result.add(c);
	}
	return result;

    }

    public int calcEntropy(ArrayList<Integer> attributeslist, ArrayList<Attribute> attr, ArrayList<Integer> exampIndex, AtomicInteger indexindex ){
    	ArrayList<Double> entropy = new ArrayList<Double>();
    	
    	//If the exampIndex is null we will instead use all the examples available.
		ArrayList<Integer> temp = new ArrayList<Integer>();
		temp.add(0);
		temp.add(1);
		temp.add(2);
		temp.add(3);
		temp.add(4);
		temp.add(5);
		temp.add(6);
		temp.add(7);
		temp.add(8);
		temp.add(9);		
		temp.add(10);
		temp.add(11);
		
    	for(Integer i: attributeslist){
    		if(exampIndex == null){
    			entropy.add(attr.get(i).calculateEntropy(goal, temp));
    		}else{
    			entropy.add(attr.get(i).calculateEntropy(goal, exampIndex));
    		}
    		
    	}
    	int index = 0;
    	for(int j = 0; j  < entropy.size(); j++){
    		if(entropy.get(j) > entropy.get(index)){
    			index = j;
    		}
    	}
    	System.out.println("\n");
    	indexindex.set(index);
	return attributeslist.get(index);
    }

    public void run() {
	ArrayList<Integer> attr = new ArrayList<Integer>(), ex = new ArrayList<Integer>();
	OutPutter op = new OutPutter();
	for(int i = 0; i < attributes.size(); i++)	//init attri index
	    attr.add(i);
	for(int i = 0; i < attributes.get(0).getData().size(); i++) //init example index
	    ex.add(i);

	TreeNode<String> result = id3(attr,ex);
	op.OutPut(result);	

    }

}
